package GreedyAlgorithm;

import java.util.HashMap;

/**
 * question: 一个整数数组，划分成小块，每个快的异或和为0，最多分成多少块
 * <p>
 * examples: [3,2,1,0,1,0,2,0,3,2,1,0,4,0] -> 7
 *
 * @author Liaorun
 */
public class MostEOR {

    public static void main(String[] args) {
        System.out.println(mostEOR(new int[]{3, 2, 1, 0, 1, 0, 2, 0, 3, 2, 1, 0, 4, 0}));
    }

    public static int mostEOR(int[] arr) {
        int xor = 0;
        // dp[i] -> arr[0..i]在最优划分的情况下，异或和为0最多的部分是多少个
        int[] dp = new int[arr.length];

        // key: 从0出发的某个前缀异或和
        // value: 这个前缀异或和出现的最晚的下标
        HashMap<Integer, Integer> map = new HashMap<>();

        map.put(0, -1);

        for (int i = 0; i < arr.length; i++) {
            // 0..i所有数的异或和
            xor ^= arr[i];
            // 上一次，这个异或和出现的位置
            if (map.containsKey(xor)) {
                Integer pre = map.get(xor);
                // [pre+1,i]可以划分成一个区域
                dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
            }

            if (i > 0) {
                // 上一个if没有进入，
                // 这里就会把当前位置划分的份数，使用上一个位置的
                // 进入了也不会影响值
                dp[i] = Math.max(dp[i - 1], dp[i]);
            }
            map.put(xor, i);
        }

        return dp[dp.length - 1];
    }
}
